| | Category | MATH | P22 | Strong Matching Preclusion of the Generalized Petersen Graph |
| | Abstract | The world wide web, cell phone lines and other technology networks |
| | depend on the strength of their networks to connect millions of people |
| | daily. Supercomputer networks are used frequently as one of the most |
| | powerful computing tools in the world. In the computer science field, it is |
| | important to detect the reliability of an interconnection network |
| | because the speed and cost of a network often depends on its design. |
| | |
| | Graph theory allows for complex networks and processes to be |
| | modeled and examined using edges and vertices. The idea of strong |
| | matching preclusion within graph theory assists with fault diagnosis, as |
| | it can specifically be used to simulate the propagation of outside |
| | interference on these large computer networks and to design optimal |
| | strategies to protect them from a real-time malware attack. The strong |
| | matching preclusion number of a graph is the minimum number of |
| | vertices and edges whose deletion results in a graph with neither |
| | perfect matchings nor almost-perfect matchings. The Petersen Graph is |
| | a strongly regular graph which provides many counterexamples to |
| | graph-theoretic statements. One can extend the Petersen graph to a |
| | variety of graphs that have many similar properties; these are known as |
| | the Generalized Petersen Graphs P(n,k). In this project, the |
| | robustness of P(n,k) was shown by proving that the graph will always be |
| | strongly matched under specific conditions. |
| | Rather than induction, the principle of casework based on parity was |
| | used to investigate the graph due to the infinite amount of base cases |
| | necessary. This more technical approach is direct and efficient; it |
| | provides insight towards other methods applicable to a related set of |
| | problems. Furthermore, the greedy algorithm was used to optimize our |
| | solutions. |
| | The class of Generalized Petersen Graphs can be extended to a 3D |
| | network which can be used for parallel computing. As shown in this |
| | project, this type of network is one that is extremely stable and efficient, |
| | even during node or connection failure. The findings in this project will |
| | allow for more effective high speed parallel and quantum computing. |
| | Bibliography | J.-H. Park and I. Ihm. Strong matching preclusion. Theoretical |
| | Computer Science. 412:6409--6419, 2011.E. Cheng, L.Lipt'ak, N. |
| | Prince, and K. Stanton. Matching preclusion and conditional matching |
| | preclusion problems for the Generalized Petersen graph |
| | 𝑃(𝑛,3). 2011. |